package codingforgreat.class18;


//lc : 934
public class Class02_ShortestBridge {
    public int shortestBridge(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        int all = M * N;
        int[] curs = new int[all];
        int[]  nexts = new int[all];
        int island = 0;
        int[][] records = new int[2][all];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(grid[i][j] == 1){
                    int queueSize = infect(grid, i, j, N, M, curs, 0, records[island]);
                    int V = 1;
                    while (queueSize != 0){
                        V++;
                        queueSize = bfs(N, M, all, V, curs, queueSize, nexts, records[island]);
                        int[] temp = curs;
                        curs = nexts;
                        nexts = temp;
                    }
                    island++;
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < all; i++) {
            min = Math.min(min, records[0][i] + records[1][i]);
        }
        return min - 3;
    }
    public int infect(int[][] grid, int i, int j, int N, int M, int[] curs, int index, int[] records){
        if(i < 0 || i >= N || j < 0 || j >= M || grid[i][j] != 1){
            return index;
        }
        grid[i][j] = 2;
        int p = i * M + j;
        curs[index++] = p;
        records[p] = 1;
       index = infect(grid, i - 1, j, N, M, curs, index, records);
       index = infect(grid, i + 1, j, N, M, curs, index, records);
       index = infect(grid, i ,j - 1, N, M, curs, index, records);
       index = infect(grid, i ,j + 1, N, M, curs, index, records);
        return index;
    }

    // 二维原始矩阵中，N总行数，M总列数
    // all 总 all = N * M
    // V 要生成的是第几层 curs V-1 nexts V
    // record里面拿距离
    public int bfs(int N, int M, int all, int V, int[] curs,
                   int size, int[] nexts,int[] record){
        int nexti = 0;
        for (int i = 0; i < size; i++) {
            // curs[i] -> 一个位置
            int up = curs[i] < M ? -1 : curs[i] - M;
            int down = curs[i] + M >= all ? -1 : curs[i] + M;
            int left = curs[i] % M == 0 ? -1 : curs[i] - 1;
            int right = curs[i] % M == M - 1 ? -1 : curs[i] + 1;
            if (up != -1 && record[up] == 0) {
                record[up] = V;
                nexts[nexti++] = up;
            }
            if (down != -1 && record[down] == 0) {
                record[down] = V;
                nexts[nexti++] = down;
            }
            if (left != -1 && record[left] == 0) {
                record[left] = V;
                nexts[nexti++] = left;
            }
            if (right != -1 && record[right] == 0) {
                record[right] = V;
                nexts[nexti++] = right;
            }
        }
        return nexti;

    }

}
